//如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数
//值排序之后中间两个数的平均值。
//
// 例如，
//
// [2,3,4] 的中位数是 3
//
// [2,3] 的中位数是 (2 + 3) / 2 = 2.5
//
// 设计一个支持以下两种操作的数据结构：
//
//
// void addNum(int num) - 从数据流中添加一个整数到数据结构中。
// double findMedian() - 返回目前所有元素的中位数。
//
//
// 示例 1：
//
// 输入：
//["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
//[[],[1],[2],[],[3],[]]
//输出：[null,null,null,1.50000,null,2.00000]
//
//
// 示例 2：
//
// 输入：
//["MedianFinder","addNum","findMedian","addNum","findMedian"]
//[[],[2],[],[3],[]]
//输出：[null,null,2.00000,null,2.50000]
//
//
//
// 限制：
//
//
// 最多会对 addNum、findMedian 进行 50000 次调用。
//
//
// 注意：本题与主站 295 题相同：https://leetcode-cn.com/problems/find-median-from-data-
//stream/
// Related Topics 设计 双指针 数据流 排序 堆（优先队列） 👍 333 👎 0


package leetcode.editor.cn;

import java.util.PriorityQueue;
import java.util.Queue;

//Java：数据流中的中位数
public class ShuJuLiuZhongDeZhongWeiShuLcof {
    public static void main(String[] args) {
        MedianFinder solution = new ShuJuLiuZhongDeZhongWeiShuLcof().new MedianFinder();
        // TO TEST
        solution.addNum(1);
        solution.addNum(2);
        System.out.println(solution.findMedian());
        solution.addNum(3);
        System.out.println(solution.findMedian());
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class MedianFinder {

        /**
         * initialize your data structure here.
         */
        /**
         * A保存较大的一半
         * B保存较小的一半
         */
        Queue<Integer> A, B;

        public MedianFinder() {
            // 小顶堆
            A = new PriorityQueue<>();
            // 大顶堆
            B = new PriorityQueue<>((x, y) -> (y - x));
        }

        /**
         * 每添加一个元素就进行排序
         * 底层存储：数组或者链表
         *
         * @param num
         */
        public void addNum(int num) {
            // 要保证A和B各占一半
            if (A.size() != B.size()) {
                // 假设把元素插入B，B的堆顶元素一定是B里面的最大值，然后把B的堆顶加入A
                // 假设把元素插入A，A的堆顶元素一定是A里面的最小的，然后把A的堆顶加入B
                // 如果是奇数，B保存的(n-1)/2,A保存了(n+1)/2，也就是A是保存的多的那份，B保存的少的那份
                A.add(num);
                B.add(A.poll());
            } else {
                // 优先保障A，当前是偶数，在加一个是奇数，而A的数量是B的数量多的
                B.add(num);
                A.add(B.poll());
            }
        }

        /**
         * 如果是奇数，取中间的值
         * 如果是偶数，取中间两个数之和的一半
         *
         * @return
         */
        public double findMedian() {
            if (A.size() != B.size()) {
                return A.peek() / 1.0d;
            } else {
                return (A.peek() + B.peek()) / 2.0d;
            }
        }
    }

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
//leetcode submit region end(Prohibit modification and deletion)

}
